package com.wengu.algorithm.alg;

import com.wengu.algorithm.dto.TaskAlg;
import com.wengu.algorithm.dto.UserAlg;
import com.wengu.algorithm.entity.AssignmentOutcome;
import com.wengu.algorithm.service.AssignmentOutcomeUserService;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.stream.Collectors;

/**
 * QEA算法
 */

@Slf4j
public class QEA {
    // 高斯核函数的sigma参数，控制权重衰减速度
    public static double sigma;
    // 权重调节参数，取值范围[0,1]
    public double alpha;
    // 权重调节参数，取值范围[0,1]
    public double gamma;
    // 权重调节参数，取值范围[0,1]
    public double mu;
    // 蚂蚁数量
    public int antCount;
    // 迭代轮数
    public int roundCount;
    // 信息素初始值
    public double initialPheromone;
    // 信息素权重参数
    public double pheromoneWeight;
    // 启发式信息权重参数
    public double heuristicWeight;
    // 信息素挥发系数
    public double evaporationRate;

    // 空间索引结构，用于快速查找附近任务
    public SpatialIndex spatialIndex;

    /**
     * 最优路径选择概率
     */
    public double bestSelectionProbability;
    // 创建线程池，根据实际情况调整线程数量
    ExecutorService executor = Executors.newFixedThreadPool(2);

    public QEA(double alpha){
        this.alpha = alpha;
    }
    public QEA(double alpha,double bestSelectionProbability){
        this.alpha = alpha;
        this.bestSelectionProbability = bestSelectionProbability;
    }
    public QEA(){
    }


    // 定义一个内部类来保存任务处理结果
    public static class TaskResult {
        TaskAlg task;
        double utility;
        double deltaF;
        boolean overBudget = false;
        boolean notIncrease = false;
    }

    /**
     * 空间索引内部类，用于高效查找附近任务
     */
    public class SpatialIndex {
        /**
         * 网格键内部类，表示网格坐标
         */
        private class GridKey {
            final int xCell;  // x轴网格坐标
            final int yCell;  // y轴网格坐标

            GridKey(int xCell, int yCell) {
                this.xCell = xCell;
                this.yCell = yCell;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                GridKey gridKey = (GridKey) o;
                return xCell == gridKey.xCell && yCell == gridKey.yCell;
            }

            @Override
            public int hashCode() {
                return Objects.hash(xCell, yCell);
            }
        }

        // 网格映射
        private final Map<String, Set<TaskAlg>> grid = new HashMap<>();
        // 网格大小
        private double cellSize;
        // 存储该任务在哪些网格的Map。key为任务id，value为网络坐标拼接（xCell-yCell）的列表
//        public final Map<Long,Set<String>> taskIdToGridKey = new HashMap<>();

        /**
         * 构造函数，构建空间索引
         * @param tasks 任务列表
         * @param searchRadius 搜索半径
         */
        public SpatialIndex(List<TaskAlg> tasks, double searchRadius) {
            // 网格大小设置为搜索半径
            this.cellSize = searchRadius;
            // 构建索引
            buildIndex(tasks);
        }

        /**
         * 构建空间索引
         * @param tasks 任务列表
         */
        private void buildIndex(List<TaskAlg> tasks) {
            for (TaskAlg task : tasks) {
                // 计算任务所在的网格坐标
                GridKey key = new GridKey(
                        (int)(task.taskX / cellSize),
                        (int)(task.taskY / cellSize)
                );
                // 将任务添加到对应网格
                String strKey = key.xCell + "-" + key.yCell;
                grid.computeIfAbsent(strKey, k -> new HashSet<>()).add(task);
//                taskIdToGridKey.computeIfAbsent(task.id, k -> new HashSet<>()).add(strKey);
            }
        }

        /**
         * 获取附近任务
         * @param x 中心点x坐标
         * @param y 中心点y坐标
         * @param radius 搜索半径
         * @return 附近任务列表
         */
        public List<TaskAlg> getNearbyTasks(double x, double y, double radius) {
            // 已检查的网格
            Set<String> checkedCells = new HashSet<>();
            // 结果列表
            List<TaskAlg> results = new ArrayList<>();

            // 计算中心网格坐标
            int centerX = (int)(x / cellSize);
            int centerY = (int)(y / cellSize);

            // 检查3x3区域确保覆盖
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    GridKey key = new GridKey(centerX + dx, centerY + dy);
                    String strKey = key.xCell + "-" + key.yCell;
                    // 如果网格未被检查过
                    if (checkedCells.add(strKey)) {
                        // 添加该网格中的所有任务
                        results.addAll(grid.getOrDefault(strKey, Collections.emptySet()));
                    }
                }
            }

            // 精确距离过滤，只保留在半径内的任务
            return results.stream()
                    .filter(t -> calculateDistance(x, y, t.taskX, t.taskY) <= sigma)
                    .collect(Collectors.toList());
        }
    }

    // 存储任务的执行次数
    public List<TaskAlg> allocateTasks(UserAlg user, List<TaskAlg> allTasks, AssignmentOutcome assignmentOutcome, AssignmentOutcomeUserService assignmentOutcomeUserService, Map<Long, TaskAlg> taskCacheMap, String algName, Set<Long> notIncreaseTaskIdSet) {


        List<TaskAlg> selected = getBestPath(user, allTasks, taskCacheMap, notIncreaseTaskIdSet);
        // 计算用户总效用值
        double userTotalDeltaF = calculateTotalDeltaF(selected);
        // 更新任务的执行次数
        updateTaskExecuteTimes(user, taskCacheMap, selected);
        // 保存用户执行结果详情表
        assignmentOutcomeUserService.saveOutcomeUser(user, assignmentOutcome, selected,userTotalDeltaF);
        log.info("用户[{}]执行平台安排的任务后的质量增量总和为[{}]",user.id,userTotalDeltaF);
        return selected;
    }

    /**
     * 更新任务的执行次数
     * @description
     * @param user
     * @param taskCacheMap
     * @param selected
     * @author wanghailei
     * @date 2025/11/3
     * @version 1.0
     */
    private void updateTaskExecuteTimes(UserAlg user, Map<Long, TaskAlg> taskCacheMap, List<TaskAlg> selected) {
        double lastX = user.startX;
        double lastY = user.startY;
        for (TaskAlg bestTask : selected) {
            double distanceCost = calculateDistance(
                    lastX, lastY,
                    bestTask.taskX, bestTask.taskY);
            bestTask.k++;
            TaskAlg taskCache = taskCacheMap.get(bestTask.id);
            if (taskCache == null) {
                taskCache = bestTask;
                taskCacheMap.put(bestTask.id, taskCache);
            } else {
                taskCache.k++;
            }
            // 选择下一个任务的总质量
            taskCache.totalF += bestTask.deltaF;
            // 计算该用户执行所有的任务的总的质量值
//                userTotalDeltaF += bestTask.deltaF;
            if (taskCache.totalF > 1) {
                log.info("任务[{}]的总质量大于1,totalF={},k={},successProb={}", taskCache.id, taskCache.totalF, taskCache.k, taskCache.successProb);
            }
            // 累加该用户的旅行成本和执行成本
            user.distanceCost += distanceCost;
            user.executionCost += bestTask.executionCost;
            user.usedCost = user.distanceCost + user.executionCost;
            lastX = bestTask.taskX;
            lastY = bestTask.taskY;
        }
        if (selected.size() > 0) {
            double finalTrip = calculateFinalTrip(selected.get(selected.size() - 1), user);
            user.distanceCost += finalTrip;
            user.usedCost = user.distanceCost + user.executionCost;
        }
    }

    public List<TaskAlg> getBestPath(UserAlg user, List<TaskAlg> allTasks, Map<Long, TaskAlg> taskCacheMap, Set<Long> notIncreaseTaskIdSet) {
        List<TaskAlg> candidateTasks = new ArrayList<>(allTasks);
        List<TaskAlg> selected = new ArrayList<>();
        Set<Long> selectedTaskIdSet = new HashSet<>();
        spatialIndex = null;
        double usedCost = 0;
        double distanceCost = 0;
        double executionCost = 0;
        while (true) {
            TaskAlg bestTask = null;
            double maxUtility = 0;
            double tailX = user.startX, tailY = user.startY;
            TaskAlg last = null;
            if (!selected.isEmpty()) {
                last = selected.get(selected.size()-1);
                tailX = last.taskX;
                tailY = last.taskY;
            }

            for (TaskAlg t : candidateTasks) {
                // 从map中取到该任务的执行次数
                TaskAlg taskCache = taskCacheMap.get(t.id);
                if (taskCache != null && taskCache.k > 0){
                    t.k = taskCache.k;
                    t.totalF = taskCache.totalF;
                }
                // 计算旅行成本
                t.distanceCost = calculateDistance(tailX, tailY, t.taskX, t.taskY);
                double totalCost = t.distanceCost + t.executionCost;
//                double weightCost = t.distanceCost + Math.log10(t.executionCost) * alpha;
//                double weightCost = t.distanceCost + Math.pow(t.executionCost , alpha);
                double weightCost = t.distanceCost + t.executionCost * alpha;
                double deltaF = t.calDeltaFCommon();
                if (deltaF <= 0) {
//                    log.info("任务[{}]的质量增量等于0,totalF={},k={}", t.id, t.totalF, t.k);
                    continue;
                }
                if (t.totalF > 1) {
                    log.info("任务[{}]的总质量大于1,totalF={},k={},successProb={}", t.id, t.totalF, t.k, t.successProb);
                    notIncreaseTaskIdSet.add(t.id);
                    continue;
                }

                // 检查添加后总成本是否超预算（包含最终返回行程）
                if (usedCost + totalCost + calculateFinalTrip(t, user) > user.budget){
                    continue;
                }
                // 计算效用函数
                double utility = calculateUtility(t, candidateTasks, weightCost,selectedTaskIdSet, notIncreaseTaskIdSet,deltaF, user.budget, user.usedCost);
//                log.info("user={},utility={}",user.id,utility);
                if (utility > maxUtility) {
                    maxUtility = utility;
                    // 更新最佳任务
                    bestTask = t;
                    t.deltaF = deltaF;
                }
            }
            if (bestTask != null) {
                selected.add(bestTask);
                selectedTaskIdSet.add(bestTask.id);
                candidateTasks.remove(bestTask);
                // 累加该用户的旅行成本和执行成本
                distanceCost += bestTask.distanceCost;
                executionCost += bestTask.executionCost;
                usedCost = distanceCost + executionCost;
            } else {
                break;
            }
        }

        return selected;
    }


    /**
     * 计算路径总质量增量
     */
    public double calculateTotalDeltaF(List<TaskAlg> path) {
        return path.stream().mapToDouble(TaskAlg::calDeltaFCommon).sum();
    }

    /**
     * 计算添加新任务产生的实际成本
     * @param currentPath 当前已选任务路径（不包含新任务）
     * @param newTask 将要添加的新任务
     * @param user 用户信息
     * @return 新增成本（移动成本 + 执行成本）
     */
    public double calculateCost(List<TaskAlg> currentPath, TaskAlg newTask, UserAlg user) {
        double distanceCost;

        if (currentPath.isEmpty()) {
            // 从用户起点到新任务的距离
            distanceCost = calculateDistance(
                    user.startX, user.startY,
                    newTask.taskX, newTask.taskY
            );
        } else {
            // 从当前路径最后一个任务到新任务的距离
            TaskAlg lastTask = currentPath.get(currentPath.size() - 1);
            distanceCost = calculateDistance(
                    lastTask.taskX, lastTask.taskY,
                    newTask.taskX, newTask.taskY
            );
        }

        return distanceCost + newTask.executionCost;
    }

    /**
     * 计算距离
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    public static double calculateDistance(double x1, double y1, double x2, double y2) {
        return euclidean(x1, y1, x2, y2);
    }

    /**
     * 欧拉距离
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    private static double euclidean(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));
    }



    /**
     * 计算从最后一个任务到终点的成本（用于预算检查）
     */
    public double calculateFinalTrip(TaskAlg lastTask, UserAlg user) {
        return calculateDistance(
                lastTask.taskX, lastTask.taskY,
                user.destX, user.destY
        );
    }

    public double calculateUtility(TaskAlg candidate, List<TaskAlg> allTasks, double weightCost, Set<Long> selectedTaskIdSet, Set<Long> taskIdSet, double deltaF, double budget, double usedCost){
        return deltaF / weightCost;
    }


    /**
     * 异步执行算法
     * @description
     * @param user
     * @param allTasks
     * @param assignmentOutcome
     * @param assignmentOutcomeUserService
     * @param taskCacheMap
     * @param algName
     * @param notIncreaseTaskIdSet
     * @return java.util.List<com.wengu.algorithm.dto.TaskAlg>
     * @author wanghailei
     * @date 2025/9/12
     * @version 1.0
     */
    public List<TaskAlg> allocateTasksAsync(UserAlg user, List<TaskAlg> allTasks, AssignmentOutcome assignmentOutcome, AssignmentOutcomeUserService assignmentOutcomeUserService, Map<Long, TaskAlg> taskCacheMap, String algName, Set<Long> notIncreaseTaskIdSet) {
        // 该用户执行完所有任务的质量增量总和
        double userTotalDeltaF = 0;

        List<TaskAlg> candidateTasks = new ArrayList<>(allTasks);
        List<TaskAlg> selected = new ArrayList<>();
        Set<Long> selectedTaskIdSet = new HashSet<>();
        while (true) {
            TaskAlg bestTask = null;
            double maxUtility = 0;
            double tailX = user.startX, tailY = user.startY;
            TaskAlg last = null;
            if (!selected.isEmpty()) {
                last = selected.get(selected.size()-1);
                tailX = last.taskX;
                tailY = last.taskY;
            }
            final double tailXFinal = tailX;
            final double tailYFinal = tailY;
            List<Future<TaskResult>> futures = new ArrayList<>();
            for (TaskAlg t : candidateTasks) {
                // 为每个任务提交一个异步任务
                futures.add(executor.submit(() -> {
                    SpatialIndex spatialIndex = null;
                    TaskResult result = new TaskResult();
                    result.task = t;

                    // 从map中取到该任务的执行次数
                    TaskAlg taskCache = taskCacheMap.get(t.id);
                    if (taskCache != null && taskCache.k > 0) {
                        t.k = taskCache.k;
                    }

                    // 计算旅行成本
                    t.distanceCost = calculateDistance(tailXFinal, tailYFinal, t.taskX, t.taskY);
                    double totalCost = t.distanceCost + t.executionCost;
                    double weightCost = t.distanceCost + t.executionCost * alpha;
                    double deltaF = t.calDeltaF();

                    if (t.totalF > 1) {
                        log.info("任务[{}]的总质量大于1,totalF={},k={},successProb={}", t.id, t.totalF, t.k, t.successProb);
                        result.notIncrease = true;
                    }

                    // 检查添加后总成本是否超预算（包含最终返回行程）
                    if (user.usedCost + totalCost + calculateFinalTrip(t, user) > user.budget) {
                        result.overBudget = true;
                        return result;
                    }

                    // 计算效用函数
                    result.utility = calculateUtility(t, candidateTasks, weightCost, selectedTaskIdSet, notIncreaseTaskIdSet, deltaF, user.budget - user.usedCost, user.usedCost);
                    result.deltaF = deltaF;

                    return result;
                }));
            }

            for (Future<TaskResult> future : futures) {
                try {
                    TaskResult result = future.get();
                    if (result.overBudget) {
                        continue;
                    }

                    if (result.notIncrease) {
                        notIncreaseTaskIdSet.add(result.task.id);
                    }

                    if (result.utility > maxUtility) {
                        maxUtility = result.utility;
                        bestTask = result.task;
                        bestTask.deltaF = result.deltaF;
                    }
                } catch (Exception e) {
                    log.error("处理任务时发生异常", e);
                }
            }

            if (bestTask != null) {
                // 先计算成本再添加任务
                double cost = calculateCost(selected, bestTask, user);
                user.usedCost += cost;
                selected.add(bestTask);
                selectedTaskIdSet.add(bestTask.id);
                candidateTasks.remove(bestTask);
                bestTask.k++;
                TaskAlg taskCache = taskCacheMap.get(bestTask.id);
                if (taskCache == null) {
                    taskCache = bestTask;
                    taskCacheMap.put(bestTask.id, taskCache);
                } else {
                    taskCache.k++;
                }
                // 选择下一个任务的总质量
                taskCache.totalF += bestTask.deltaF;
                // 计算该用户执行所有的任务的总的质量值
                userTotalDeltaF += bestTask.deltaF;
                if (taskCache.totalF > 1) {
                    log.info("任务[{}]的总质量大于1,totalF={},k={},successProb={}", taskCache.id, taskCache.totalF, taskCache.k, taskCache.successProb);
                }
                // 累加该用户的旅行成本和执行成本
                user.distanceCost += bestTask.distanceCost;
                user.executionCost += bestTask.executionCost;
            } else {
                break;
            }
        }
        if (selected.size() > 0) {
            double finalTrip = calculateFinalTrip(selected.get(selected.size() - 1), user);
            user.distanceCost += finalTrip;
        }
        // 保存用户执行结果详情表
        assignmentOutcomeUserService.saveOutcomeUser(user, assignmentOutcome, selected,userTotalDeltaF);
        log.info("用户[{}]执行平台安排的任务后的质量增量总和为[{}]",user.id,userTotalDeltaF);
        return selected;
    }


}